package alg20241123;

import java.util.Arrays;

public class Text {
    int[] tmp;
    int ret;
    public int reversePairs(int[] record) {
        tmp = new int[record.length];
        marge(0, record.length - 1, record);
        return ret;
}
    public void marge(int left, int right, int[] nums){
        if(left >= right) return;
        int mid = (left + right) / 2;
        //分裂数组
        marge(left, mid, nums);
        marge(mid + 1, right, nums);

        //合并数组
        int cur1 = left;
        int cur2 = mid + 1;
        int i = 0;
        while(cur1 <= mid && cur2 <= right){
            if(nums[cur1] <= nums[cur2]){
                tmp[i++] = nums[cur1++];
            }else{
               ret += mid - cur1 + 1;
                tmp[i++] = nums[cur2++];
            }
        }
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];

        //将新数组复制到旧数组
        for (int j = left; j <= right; j++) {
            nums[j] = tmp[j - left];
        }
    }

    public static void main(String[] args) {
        int[] nums = {7,5,6,4};
        Text text = new Text();
        text.reversePairs(nums);
        System.out.println(Arrays.toString(nums));
    }
}
